L2-046 天梯赛的赛场安排

题目 L2-046 天梯赛的赛场安排

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};

const int inf = 0x3f3f3f3f;

using PSI = pair<string,int>;

multiset<int> classrooms;//记录每个教室剩余多少位置

priority_queue<int> pq; //按照尚未安排赛场的队员人数从大到小的顺序，每一轮对当前未安排的人数最多的学校进行处理。

int main() {

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n,c;cin>>n>>c;

	for(int i=0;i<n;i++){

		string schools;int peoples;cin>>schools>>peoples;

		cout<<schools<<" "<<ceil(peoples*1.0/c)<<endl;

		pq.push(peoples);

	}

	while(!pq.empty()){

		int n=pq.top();pq.pop();

		if(n==0) continue;

		if(n>=c){

			classrooms.insert(0);

			pq.push(n-c);

		}else{

			auto it=classrooms.lower_bound(n);

			if(it!=classrooms.end()){

				int remain=*it;

				classrooms.erase(it);

				classrooms.insert(remain-n);

			}else{

				classrooms.insert(c-n);

			}

		}

	}

	cout<<classrooms.size()<<endl;

	return 0;

}

同类题型

视频讲解

⬅️ L2-045 堆宝塔 🏠 00-天梯赛 ➡️ L2-047 锦标赛